#ifndef xpack_test_algo_sort
#define xpack_test_algo_sort
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::test_algo_sort::inc
#include"test/helper.hpp" // 需要放第一
#include"algo/sort.hpp"
#include"interface/seqptr.hpp"
#include"math/random.hpp"
#include"mixc.hpp"
#include"utils/array.hpp"


#include"algo/heap_root.hpp"
#include<array>
#include<algorithm>
#pragma pop_macro("xuser")

namespace mixc::test_algo_sort::origin{
    struct item{
        u32 value   : 31;
        u32 mark    : 1;
    };

    xtest("heap_root") {
        // item buf[16] = {};
        // buf[0].value = 5441;
        // buf[1].value = 5441;
        // buf[2].value = 5451;
        // buf[3].value = 5450;

        // inc::array<item*, 10> ary;

        // for(uxx i = 0; i < 4; i++){
        //     ary[i] = &buf[i];
        // }

        // auto cmp = [](auto const & left, auto const & right) -> ixx {
        //     if (left->value == right->value){ return 0; }
        //     return left->value < right->value ? -1 : 1;
        // };
        
        // item new_item{ .value = 5451, .mark = 0 };
        // inc::heap_root::push(ary, 4, &new_item, cmp);

        // for(uxx i = 0; i < 5; i++){
        //     if (ary[i]->mark){
        //         xhint(i);
        //     }
        //     ary[i]->mark = 1;
        //     xhint(ary[i], u32(ary[i]->value));
        // }
    };

    xtest("sort") {
        return;
        using namespace inc;

        item buf_a[100];
        item buf_b[100];

        std::array<u32, 100> a;
        inc::array<u32, 100> b;

        std::array<item *, 100> c = {};
        inc::array<item *, 100> d = {};
        auto cmp = [](auto const & left, auto const & right){
            return left->value < right->value;
        };

        auto cmpx = [](auto const & left, auto const & right) -> ixx {
            if (left->value == right->value){ return 0; }
            return left->value < right->value ? -1 : 1;
        };

        for(uxx i = 1; i < 100; i++){
            for(uxx j = 0; j < 1000; j++){
                for(uxx k = 0; k < i; k++){
                    buf_a[k].value = buf_b[k].value = a[k] = b[k] = random<u32>();
                    buf_a[k].mark = 0;
                    buf_b[k].mark = 0;
                    c[k] = &buf_a[k];
                    d[k] = &buf_b[k];
                }

                auto subseq = inc::seqptr<u32>(b).subseq(co{0, i});
                auto subseqx = inc::seqptr<item *>(d).subseq(co{0, i});

                std::sort(a.begin(), a.begin() + i);
                std::sort(c.begin(), c.begin() + i, cmp);
                inc::sort::heap(subseq);
                inc::sort::heap(subseqx, cmpx);
                

                // for(uxx ii = 0; ii < subseq->length; ii++){
                //     auto item = c[ii];
                //     xhint(u32(item->value));
                // }

                // subseqx.foreach([](auto cell){
                //     xhint(u32(cell->value));
                // });

                // continue;

                for(uxx k = 0; k < subseq->length; k++){
                    xassert_eq(a[k], subseq[k], k, a[k], subseq[k]);

                    xassert_eq(c[k]->value, subseqx[k]->value, k, c[k]->value, subseqx[k]->value){
                        for(uxx ii = 0; ii < subseq->length; ii++){
                            auto item = c[ii];
                            xhint(u32(item->value));
                        }

                        subseqx.foreach([](auto cell){
                            xhint(u32(cell->value));
                        });

                        break;
                    }
                }

                for(uxx k = 0; k < subseqx->length; k++){
                    xassert_eq(c[k]->mark, 0u, k);
                    xassert_eq(subseqx[k]->mark, 0u, k);
                    c[k]->mark = 1;
                    subseqx[k]->mark = 1;
                }
            }
        }
    };
}

#endif
